package cn.edu.xjtu.hash.designKey.groupAnagrams;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 字母异位词分组
 * 
 * 给定一个字符串数组，将字母异位词组合在一起。可以按任意顺序返回结果列表. 字母异位词指字母相同，但排列不同的字符串。
 */
public class Solution {
  public static void main(String[] args) {
    String[] strs = new String[] { "eat", "tea", "tan", "ate", "bat", "nat" };
    System.out.println(groupAnagrams(strs));
  }

  public static List<List<String>> groupAnagrams(String[] strs) {
    List<List<String>> ret = new ArrayList<>();
    Map<String, Integer> map = new HashMap<>();
    for (String str : strs) {
      String temp = sortStr(str);
      if (map.containsKey(temp)) {
        List<String> tempList = ret.get(map.get(temp));
        tempList.add(str);
        ret.remove((int) map.get(temp));
        ret.add(tempList);
        map.put(temp, ret.size() - 1);
      } else {
        List<String> tempList = new ArrayList<>();
        tempList.add(temp);
        ret.add(tempList);
        map.put(temp, ret.size() - 1);
      }
    }
    return ret;
  }

  public static String sortStr(String str) {
    char[] chars = str.toCharArray();
    Arrays.sort(chars);
    return new String(chars);
  }
}
